{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#不限制顺序，不合题意\n",
    "from typing import List \n",
    "def GetCombinePos(nums, pos,n, k, out): #选取第pos+1个数\n",
    "    if(pos == k - 1):\n",
    "        for i in range(pos, n):\n",
    "            nums[pos], nums[i] = nums[i], nums[pos]\n",
    "            out.append(nums[0:k])\n",
    "            nums[pos], nums[i] = nums[i], nums[pos]\n",
    "    else:\n",
    "        for i in range(pos, n):\n",
    "            nums[pos], nums[i] = nums[i], nums[pos]\n",
    "            GetCombinePos(nums, pos+1, n, k, out)\n",
    "            nums[pos], nums[i] = nums[i], nums[pos]\n",
    "    \n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = [x for x in range(1, n+1)]\n",
    "        out = []\n",
    "        GetCombinePos(nums, 0, n, k, out)\n",
    "        return out\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#正确解法（500ms）：\n",
    "from typing import List \n",
    "def GetCombinePos(nums,start,end, pos, k, sel, out):\n",
    "    if(pos == k - 1):\n",
    "        for i in range(start, end+1):\n",
    "            sel[pos] = nums[i]\n",
    "            out.append(sel.copy())\n",
    "    elif(pos < k - 1):\n",
    "        for i in range(start, end):\n",
    "            sel[pos] = nums[i]\n",
    "            GetCombinePos(nums, i + 1, end, pos+1, k, sel, out)\n",
    "    \n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = [x for x in range(1, n+1)]\n",
    "        out = []\n",
    "        sel = [0] * k\n",
    "        GetCombinePos(nums, 0, n-1, 0, k, sel, out)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "#正确解法（80ms）：\n",
    "from typing import List \n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        out = []\n",
    "        sel = [0] * k\n",
    "        def backtrack(start, k):\n",
    "            if(k == 1):\n",
    "                for i in range(start,  n + 1):\n",
    "                    sel[-k] = i\n",
    "                    out.append(sel.copy())\n",
    "            elif(k > 1):\n",
    "                for i in range(start, n + 2 - k):\n",
    "                    sel[-k] = i\n",
    "                    backtrack( i + 1, k-1)\n",
    "        backtrack(1, k)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#更优解法：\n",
    "#gary757483617\n",
    "#1 年前\n",
    "# 执行用时 : 96 ms, 在Combinations的Python提交中击败了100.00% 的用户# 终于骄傲一次。\n",
    "#这题让我想到了排列组合的性质C(m,n)=C(m-1,n)+C(m-1,n-1)\n",
    "\n",
    "class Solution(object):\n",
    "    def combine(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if k>n or k==0:\n",
    "            return []\n",
    "        if k==1:\n",
    "            return [[i] for i in range(1,n+1)]\n",
    "        if k==n:\n",
    "            return [[i for i in range(1,n+1)]]\n",
    "        \n",
    "        answer=self.combine(n-1,k)\n",
    "        for item in self.combine(n-1,k-1):\n",
    "            item.append(n)\n",
    "            answer.append(item)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n"
     ]
    }
   ],
   "source": [
    "a = Solution()\n",
    "print(a.combine(4,5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Input: n = 4, k = 2\n",
    "Output:\n",
    "[\n",
    "  [2,4],\n",
    "  [3,4],\n",
    "  [2,3],\n",
    "  [1,2],\n",
    "  [1,3],\n",
    "  [1,4],\n",
    "]\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/combinations\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
